蟻本2-5 Conscription
code: python
class UnionFindTree():
# n要素で初期化
def __init__(self, n):
self.n = n
self.par = list(range(n))
self.rank = 0 * n
# 木の根を求める
def find(self, x):
if self.parx == x:
return x
else:
self.parx = self.find(self.parx)
return self.parx
# xとyの属する集合を併合
def unite(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.rankx < self.ranky:
self.parx = y
else:
self.pary = x
if self.rankx == self.ranky:
self.rankx += 1
# xとyが同じ集合に属するか否か
def same(self, x, y):
return self.find(x) == self.find(y)
def kruskal():
es.sort() # 辺のコストが小さい順にソートする
UFT = UnionFindTree(V) # Union-Findの初期化
res = 0
for i in range(E):
e = esi
if not UFT.same(e1, e2):
UFT.unite(e1, e2)
res += e0
return res
MAX_R = 50000
# 入力
N, M, R = map(int,input().split())
x = 0 * MAX_R
y = 0 * MAX_R
d = 0 * MAX_R
for i in range(R):
xi, yi, di = map(int,input().split())
V = N + M
E = R
es = []
for i in range(R):
es.append([-di, N + xi, yi])
print(10000 * (N + M) + kruskal())
# 5 5 8
# 4 3 6831
# 1 3 4583
# 0 0 6592
# 0 1 3063
# 3 3 4975
# 1 3 2049
# 4 2 2104
# 2 2 781
テーマ
#UnionFind